1. Field of the Invention
The present invention generally relates to the field of visualizing dynamic graphs and in particular to a method and an apparatus for animating transitions among a dynamic graph series.
2. Description of Related Art
Dynamic graphs, compared with static graphs, are changed over time. Graph elements (nodes/edges) will be added or removed or their attributes will be changed dynamically. The major purpose of visualizing dynamic graphs is to facilitate disclosing the change patterns along the time dimension. This will expose the essence of the graphs or network evolutions such as the evolutions of social communities in a social network.
Many challenges exist in dynamic graph visualization. One of the most important challenges is to smoothly transit graph changes between different time frames to keep users' focus. In particular, graph changes may be further classified into the following categories: 1. graph change due to removal of an element; 2. graph change due to addition of an element; and 3. graph change due to change of an attribute of an existing element. Removing or adding elements in a dynamic graph will directly change the topology. It is a significant change in a graph. Without any animated transitions, users might lose their focus and are confused about the sudden graph change. While the third type of graph change will be slighter, and it usually leads to the moving of the elements.
To visualize the above graph changes while preserving the user's mental map, several animating methods have been designed by dynamic graph visualization systems in the prior art. The latest and most powerful system is Sonia (see http://sonia.stanford.edu). The system provides a total solution of dynamic graph visualization including animated transition. In the system, edge driven animation is used to smoothly transit both the topology changes and attribute changes. All the nodes are initially laid out on the display (the isolated nodes are usually laid out on a circle). Edges are dynamically added or removed between nodes. The added or removed edges will drag two connected nodes together or release these nodes to their initial positions. The edge lengths are in inverse ratio to the edge weights. The changing of edge weights will lead to the movements of the connected nodes. The nodes are moved along a straight line path when animating. It is quite efficient and clear when the number of the changed elements is small. However, when the number of the changed elements is large, this edge driven transition method may produce visual clutter due to long moving distances of the nodes and a tendency that the moved elements are likely to overlap. Furthermore, in most cases, node elements are also added into or removed from the dynamic graph frequently. The edge driven animated transition method will not be enough.